
 public class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }


class Solution {

    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
        ListNode newHead = new ListNode(-1);

        if(headA == null && headB == null){
            return null;
        }

        ListNode cur = newHead;

        while(headA != null && headB != null){
            if(headA.val < headB.val){
                if(cur == null){
                    cur = headA;
                }else{
                    cur.next = headA;
                    cur = cur.next;
                }
                headA = headA.next;

            }else{
                if(cur == null){
                    cur = headB;
                }else{
                    cur.next = headB;
                    cur = cur.next;
                }
                headB = headB.next;
            }
        }

        if(headA == null){
            cur.next = headB;
        }
        if(headB == null){
            cur.next = headA;
        }

        return newHead.next;

    }
}